#include <iostream>
using namespace std;

struct node
{ int info;
  node *next;
  node(int x=0, node* p=NULL)
  { info = x; next = p; }
};

struct List
{ node *first;
  node *last;
  List()
  { first=last=NULL; }
};
    
void push_back(List &L, node *t)
{ if(L.last==NULL) L.first=L.last=t;
  else { L.last->next = t; L.last=t;  }  
}

void push_back(List &L, int x)
{ push_back(L,new node(x,NULL)); }

void show_list(List L)
{ node *p=L.first;
  while(p!=NULL)
  { cout << p->info << " ";
    p = p->next;
  }
  cout << endl;
}    

void merge(List &L1, List &L2, List &R)
{  
  node *p=L1.first, *q=L2.first; 
  while(p!=NULL && q!=NULL)
  { if(p->info <= q->info)
    { push_back(R,p); p = p->next; }
    else
    { push_back(R,q); q = q->next; }
  }   
    
  while(p!=NULL)
  { push_back(R,p); p = p->next; }
    
  while(q!=NULL)
  { push_back(R,q); q = q->next; }
  
  R.last->next = NULL;
  L1.first=L1.last=NULL;
  L2.first=L2.last=NULL;
  
}    

void split(List &R, List &L1, List &L2)
{ int n=0;
  node *p=R.first;
  while(p != NULL) 
  { n++; p = p->next; }
  
  n = n/2;
  
  L1.first = R.first;
  p = R.first;
  for(int i=2; i<=n; i++)
    p = p->next;
  L1.last = p;
  L2.first = p->next;
  L2.last = R.last;  
  
  L1.last->next = NULL;
  R.first=R.last=NULL;
}    

void merge_sort(List &R)
{
  if (R.first == R.last) return;
  
  List L1, L2;
  split(R, L1, L2);
  merge_sort(L1);
  merge_sort(L2);
  merge(L1, L2, R);    
}


int main()
{ List L1, L2, R;
  
  push_back(R,20);
  push_back(R,10);
  push_back(R,15);
  push_back(R,34);
  push_back(R,45);
  push_back(R,30);
  push_back(R,25);
  
  show_list(R);
  
  merge_sort(R);
  
  show_list(R);
  
         
  return 0;
}    
